package _剑指offer._回溯;

import java.util.*;

/**
 * @author Liu Huan
 */

public class __电话号码总结体型 {
	public static void main(String[] args) {
		String str1 = "abc";
		String str2 = "def";
		String str3 = "ghi";
		backtrack(str1, str2, str3, 0);
		for (String str : ans) {
			System.out.print(str + "\t");
		}
	}
	
	private static List<String> ans = new ArrayList<>();
	private static StringBuilder stringBuilder = new StringBuilder();
	
	public static void backtrack(String str1, String str2, String str3, int index){
		if(stringBuilder.length()==3){
			ans.add(stringBuilder.toString());
			return;
		} else {
			if (index==0){
				for (int i = 0; i < str1.length(); i++) {
					stringBuilder.append(str1.charAt(i));
					backtrack(str1, str2, str3, index+1);
					stringBuilder.deleteCharAt(index);
				}
			}
			if(index==1){
				for (int i = 0; i < str2.length(); i++) {
					stringBuilder.append(str2.charAt(i));
					backtrack(str1, str2, str3, index+1);
					stringBuilder.deleteCharAt(index);
				}
			}
			if(index==2){
				for (int i = 0; i < str2.length(); i++) {
					stringBuilder.append(str3.charAt(i));
					backtrack(str1, str2, str3, index+1);
					stringBuilder.deleteCharAt(index);
				}
			}
			
		}
	}
}
